1. Field of the Invention
The present invention relates to an associative-memory apparatus which is used for an apparatus for information processing such as color or gray scale image compression and image recognition, and which has a function of searching for data in which the Manhattan distance is a minimum by fully-parallel processing.
2. Description of the Related Art
In recent years, in the field of information processing, in particular, of image compression and image recognition, an associative memory apparatus having a function of searching for minimum distance data has been given attention. The associative memory apparatus is one of the typical memories having a function of searching for data most similar (closest) to input information data (search data) from among a plurality of reference data registered in advance. Then, due to the excellent searching function, the associative memory apparatus is expected, when the associative memory apparatus is used for an application requiring a pattern matching function such as image compression and image recognition described above, to be able to greatly improve the performance of the pattern matching.
Here, the distance means a degree of inconsistency when search data and reference data are compared with one another, and it has been known that there are mainly the Hamming distance and the Manhattan distance. Given that the search data is SW={SW1, SW2, . . . , SWW}, and the reference data stored in i row of the memory is REFi={REFi1, REFi2, . . . , REFiW}, the Hamming distance between the ith reference data and the search data is expressed by:
                              D                      Hamm            ,            i                          =                                            ∑                              j                =                1                            W                        ⁢                          SW              j                                +                      REF            ij                                              (        1        )            The Manhattan distance follows:
                              D                      Manh            ,            i                          =                              ∑                          j              =              1                        W                    ⁢                                                                SW                j                            -                              REF                ij                                                                                    (        2        )            
The Hamming distance DHamm is mainly used for recognizing data sequences, sound, characters, and the like, and the Manhattan distance DManh is used for color or gray scale image compression/image recognition. As the fully-parallel type associative memory apparatuses which have been developed until now, a distance calculating circuit for searching for the a Hamming distance has been realized (refer to Document 1). However, there is no fully-parallel type associative memory apparatus in which a function of searching for the Manhattan distance needed for color or gray scale image compression/image recognition, or the like is realized at the memory region of the associative memory.
On the other hand, a system in which the Manhattan distance is encoded by using an associative memory for searching for the Hamming distance has been proposed (refer to Document 2). However, in this system, the circuit area is rapidly made large when the number of bits of each pattern is greater than or equal to 4 bits, and there is the problem that the electric power consumption increases accompanying with an increase in the circuit area. Further, in order to realize a Manhattan distance calculating circuit, it suffices that a circuit of calculating the absolute value of difference between the search data and the reference data is realized. However, in the case of using a subtracter (an adder) or an absolute value calculating circuit which have been conventionally known, there is the defect that the circuit scale (the number of transistors) become large.    [Document 1] H. J. Mattausch et al., “Compact associative-memory architecture with fully-parallel search capability for the minimum Hamming distance”, IEEE Journal. of Solid-State Circuits, Vol. 37, pp. 218–227, 2002.    [Document 2] H. J. Mattausch et al., “Fully-parallel pattern-matching engine with dynamic adaptability to Hamming or Manhattan distance”, 2002 Symposium on VLSI Circuit Dig. of Tech. Papers, pp. 252–255, 2002.    [Document 3] H. J. Mattausch et al., “An architecture for compact associative memories with deca-ns nearest-match capability up to large distance”, ISSCC Dig. of Tech. Papers. pp. 170–171.    [Document 4] Jpn. Pat. Appln. KOKAI Publication No. 2002-288985    [Document 5] Jpn. Pat. Appln. KOKAI Publication No. 2004-005825    [Document 6] Jpn. Pat. Appln. KOKAI Publication No. 2004-013504